A cache memory is a high-speed buffer located between a host(s) and a disk device(s), which is meant to reduce the overall latency of Input/Output (I/O) activity between the storage system and a host accessing data on the storage system. Whenever a host requests data stored in a memory system, the request may be served with significantly lower latency if the requested data is already found in cache, since this data must not be brought from the disks. As of the year 2004, speeds of IO transactions involving disk activity are typically on the order of 5-10 milliseconds, whereas IO speeds involving cache (e.g. RAM memory) access are on the order of several nanoseconds.
The relatively high latency associated with disk activity derives from the mechanical nature of the disk devices. In order to retrieve requested data from a disk based device, a disk controller must first cause a disk reading arm to physically move to a track containing the requested data. Once the head of the arm has been placed at the beginning of a track containing the data, the time required to read the accessed data on the relevant track is relatively very short, on the order of several microseconds.
One criteria or parameter which is often used to measure the efficiency of a cache memory system or implementation is a criteria referred to as a “hit ratio”. A hit ratio of a specific implementation is the percentage of “data read” requests issued by the host that are already found in cache and that consequently did not require time intensive retrieval from disk operations. An ideal cache system would be one reaching a 100% hit ratio.
Intelligent cache algorithms aimed at raising the level of hit ratio to a maximum often implement in the cache (amongst other things) replacement procedures that establish a “discard priority”. The discard priority relates to data portions which are already stored in the cache, and is responsible for managing the order by which each of the data portions that are currently stored in the cache are to be discarded. The various approaches to the management of the discard priority queue attempt to anticipate which of the data portions currently stored in the cache are the least likely to be requested by the host, and set the priority queue accordingly. Thus, whenever cache space is required for fetching new data into the cache, the discard priority queue is consulted, and the data portions which have been determined to be the least likely to be requested by the host are discarded first, in order to free up cache storage space which may be used for storing the newly fetched data. From another perspective, the various approaches to the management of the discard priority queue are intended to increase the likelihood that those portions of data that have been determined to be the most likely to be requested by the host will not be discarded prematurely in order to free up space or for any other purpose.
The link between certain data portions in the cache is significant for the purposes of replacement procedures. When a certain data portion has been addressed by a host as part of a certain group of operatively linked data portions or as part of a certain file, for example, it is likely that when that data portion is next addressed it will be addressed as part of the group or as part of the file, rather than as an isolated data portion. Furthermore, while the usage of the cache's memory resources grows with the amount of data fetched into the cache, fetching-time does not increase with the amount of data to be fetched into the cache. Thus, while fetching a large group and a small group (e.g., one) of linked data portions will require substantially the same amount time, discarding the larger group of linked data will free-up substantially more storage space.
Accordingly, it would be beneficial to manage the cache in terms of groups of operatively linked data portions, rather than in terms of discrete data portions. Furthermore, it would be beneficial to assign a discard priority to such groups of operatively linked data portions at least in accordance with the size each group. Yet furthermore, it would be beneficial to assign a discard priority to such groups of operatively linked data portions, such that, all other things being equal, larger groups are assigned with a higher priority to be discarded.